#include<bits/stdc++.h>
using namespace std;
const int maxn=2e3+2,maxm=5e6+2;
int mod;
int T,m,n;
int fac[maxm],inv_fac[maxm];
void upd(int &x,int v){((x+=v)>=mod)?(x-=mod):x;}
int f_pow(int x,int p){
    int ret=1;
    while(p){
        if(p%2)ret=1ll*ret*x%mod;
        x=1ll*x*x%mod;
        p/=2;
    }
    return ret;
}
void pre_calc(){
    fac[0]=1;
    for(int i=1;i<=maxm-1;i++)fac[i]=1ll*i*fac[i-1]%mod;
    inv_fac[maxm-1]=f_pow(fac[maxm-1],mod-2);
    for(int i=maxm-1;i;i--)inv_fac[i-1]=1ll*i*inv_fac[i]%mod;
    return ;
}
int calc_C(int a,int b){
    if(a<0||b<0||a<b)return 0;
    return 1ll*fac[a]*inv_fac[b]%mod*inv_fac[a-b]%mod;
}
int main(){
    freopen("pr.in","r",stdin);
    freopen("pr.out","w",stdout);
    scanf("%lld",&mod);
    scanf("%d",&T);
    pre_calc();
    while(T--){
        scanf("%d%d",&n,&m);
        // printf("calc wo %d %d %d\n",calc_C(4,2),n,m);
        int sum,ans=0,inv=f_pow(m+1,mod-n-1);
        for(int i=0;i<=n*m;i++){
            sum=0;
            for(int j=0;j<=n&&j*(m+1)<=i;j++)upd(sum,1ll*((j&1)?(mod-1):1)*calc_C(i+n-1-j*(m+1),n-1)%mod*calc_C(n,j)%mod);
            // if(T==0)printf("ca %d %d\n",i,sum);
            sum=1ll*sum*inv%mod;
            upd(ans,1ll*sum*sum%mod);
        }
        ans=1ll*(mod+1-ans)*f_pow(2ll,mod-2)%mod;
        printf("%d\n",ans);
    }
    return 0;
}